package basic.study.algorithms.solution.SlipWindow;

import java.util.ArrayDeque;

/**
 * @author Kevin
 * @date 2020/3/10 11:44
 */
public class Max_Val_239 {
    ArrayDeque<Integer> deq = new ArrayDeque();
    int[] nums;

    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if(n * k == 0) return nums;
        if(k == 1) return nums;

        this.nums = nums;

        //首先初始化窗口
        int maxIds = 0;
        for(int i = 0; i < k; i++) {
            cleanDeq(i, k);
            deq.addLast(i);
            if(nums[i] > nums[maxIds]) maxIds = i;
        }
        int[] output = new int[n - k + 1];
        output[0] = nums[maxIds];

        //然后滑动~
        for(int i = k; i < n; i++) {
            cleanDeq(i, k);
            deq.addLast(i);
            output[i - k + 1] = nums[deq.getFirst()];
        }
        return output;
    }

    public void cleanDeq(int i,int k) {
        //首先去除滑出窗口的
        if(!deq.isEmpty() && deq.getFirst() == i - k) {
            deq.removeFirst();
        }
        //然后去除小于当前值的
        while(!deq.isEmpty() && nums[deq.getLast()] < nums[i]) {
            deq.removeLast();
        }
    }
}

